/*
 * Mailbox Driver Implementation
 * Ben Marks, Chris Lekas; Operating Systems Spring 2014 
 * 
 * Implements the driver interface functions for opening, closing,
 * reading and writing to a mailbox character device. Information can
 * be printed out using the ioctl function, which prints copious
 * status information to system logs.
 * 
 */


/* Necessary includes from other parts of the Linux Kernel */
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/init.h>
#include <linux/fs.h>
#include <linux/wait.h>
#include <linux/list.h>
#include <asm/uaccess.h>
#include <linux/cdev.h>
#include <asm/current.h>
#include <linux/sched.h>

/* Compile Time Constants */
#define MYMAILBOXDEV_MAJOR  166        // Device major number 
#define MYMAILBOXDEV_NAME   "mailbox"  // Device name
#define MYMAILBOXDEV_NUM    8          // Number of mailboxes
#define MYMAILBOXDEV_SIZE   32         // Mailbox buffer size

/* Function Prototypes */

// Read from the device
ssize_t mychardev_read( struct file *fp, 
			char __user *buff, 
			size_t len, 
			loff_t *offset);
// Write to the device
ssize_t  mychardev_write(struct file *fp, 
			 const char __user *buff, 
			 size_t len, 
			 loff_t *offset);
// Initialize a device
int mychrdev_open(struct inode *in, 
		  struct file *fp);

// Close a device
int mychardev_release(struct inode *in, 
		      struct file *fp);

// Print out mailbox status information
int mychardev_ioctl(struct inode *in, 
		    struct file *fp,
		    unsigned int unused1, 
		    unsigned long unused2);

/* A mailbox struct contains all of the state for a read
   and write end of a mailbox */
struct mailbox {
  char buf [MYMAILBOXDEV_SIZE];   // Contains data in mailbox currently

  /* Block processes trying to open read end, if another process is
     already reading */
  struct semaphore readLock;
  wait_queue_head_t readQueue;


  /* Block processes trying to open write end, if another process is
     already writing */
  struct semaphore writeLock;
  wait_queue_head_t writeQueue;

  /* Ensure mutually exclusive access to shared data buffer between
     reader and writer process */
  struct semaphore bufLock;
  
  /* Block the reader if it needs to read data and none are available.
     The writer will take care of waking up the reader once more data
     are available */
  struct semaphore blockedReader;
  wait_queue_head_t blockedReaderQ;

  /* Block the writer if it needs to write data and the buffer is full.
     The reader will take care of waking up the writer once the reader has
     read some characters from the buffer. */
  struct semaphore blockedWriter; 
  wait_queue_head_t blockedWriterQ;
 
  
  int readOffset;   // Offset into buffer where next character will
                    // be read from.
  int writeOffset;  // Offset into buffer where next character will
                    // be written.
  int numItems;     // Number of characters currently in buffer that
                    // can be read.
  int numHoles;     // Number of slots that characters can safely be
                    // written to.

  /* Per Linux Device Drivers, 3rd Edition: 
     
       "Both the read and write methods return a negative value if an
       error occurs. A return value greater than or equal to 0,
       instead, tells the calling program how many bytes have been
       successfully transferred. If some data is transferred correctly
       and then an error happens, the return value must be the count
       of bytes successfully transferred, and the error does not get
       reported until the next time the function is called.

       Implementing this convention requires, of course, that your
       driver remember that the error has occurred so that it can
       return the error status in the future."

     Store an errno value to return on the next call to read
     or write, if a prior call failed after some characters
     had been successfully read or written to. 
  */
  int errnoRead;  // When nonzero, errno to return on next read call
  int errnoWrite; // When nonzero, errno to return on next write call

  /* Current reader and writer pids */
  pid_t currRead;
  pid_t currWrite;
  
  /* Minor number assiated with read and write end associated
     with this mailbox struct */
  int writeID;
  int readID;

  /* Keep track of who is waiting where */
  int numWritersWaiting; // Processes waiting to open write end
  int numReadersWaiting; // Processes waiting to open read end
  int numWritersBlocked; // Writers waiting for readers to read data
  int numReadersBlocked; // Readers waiting for writers to write data

  /* cdev struct associated with the read and write end of the mailbox. */
  struct cdev reader;
  struct cdev writer;

};

/* Global Variables */

/* The mailboxes array stores all of the mailbox structs
   in the kernel. */
static struct mailbox mailboxes[MYMAILBOXDEV_NUM / 2];


// File operations on mailbox pseudo devices
struct file_operations mbox_ops = { 
  .owner = THIS_MODULE,
  .read  = mychardev_read, 
  .write = mychardev_write, 
  .ioctl = mychardev_ioctl,
  .open  = mychrdev_open, 
  .release = mychardev_release
};

/*
  printMailbox: A helper function that prints out the following
  characteristics about a given mailbox:
  => Read and write end minor device numbers
  => Current PID of readers and writers
  => Number of processes waiting to become readers and writers, and 
     their associated PIDs.
  => Current offset for readers and writers in the buffer
  => Current number of readable characters stored in buffer, or < 0
     when reader is waiting.
  => Mailbox contents '-' indicates unintialized data

  Parameters: struct mailbox * mb: Pointer to mailbox to print information
  about.

  Returns: 0 on success; -1 on error acquiring a mutex on shared data.
 */
static int printMailbox( struct mailbox * mb ) {

  // Declare variables used to iterate through lists and waitqueues
  int i;
  struct list_head * tmp2;
  struct list_head * next2; 


  printk("#################################\n");
  printk("Mailbox Write End ID: %d\n", mb->writeID);
  printk("Mailbox Read End ID: %d\n", mb->readID);

  // Lock information about current writers and waiting writers
  if ( down_interruptible( &(mb->writeLock) ) ) {
    return -1;
  }
  printk("Writer Current PID: %d\n", mb->currWrite);
  printk("%d Writers Waiting: ", mb->numWritersWaiting );
  
  // Print out waiting writers
  list_for_each_safe( tmp2, next2, &(mb->writeQueue.task_list) ) {
    wait_queue_t * curr = list_entry( tmp2, wait_queue_t, task_list);
    struct task_struct * ts = curr->private;
    printk(" %d ", (int) ts->pid );
  }
  printk("\n");

  // Done with information about current writers and waiting writers
  up( &(mb->writeLock) );

  // Lock information about current readers and waiting readers
  if ( down_interruptible( &(mb->readLock) ) ) {
    return -1;
  }
  printk("Reader Current PID: %d\n", mb->currRead);
  printk("%d Readers Waiting: ", mb->numReadersWaiting );

  // Print out waiting readers
  list_for_each_safe( tmp2, next2, &(mb->readQueue.task_list) ) {
    wait_queue_t * curr = list_entry( tmp2, wait_queue_t, task_list);
    struct task_struct * ts = curr->private;
    printk(" %d ", (int) ts->pid );
  }
  printk("\n");

  // Done with information about current readers and waiting readers
  up( &(mb->readLock) );

  // Lock information about the buffer
  if ( down_interruptible( &(mb->bufLock) ) ) {
    return -1;
  }
  
  // Print out buffer contents information
  printk("Writer Current Offset: %d\n", 
	 (mb->writeOffset) );
  printk("Reader Current Offset: %d\n", mb->readOffset);
  printk("Mailbox Data Length: %d\n", mb->numItems);

  // Print out mailbox contents, one char at a time 
  // since '\0' is a valid mailbox character
  printk("Mailbox Contents: ");
  for ( i = 0; i < MYMAILBOXDEV_SIZE; i ++ ) {
    printk("%c", mb->buf[i]);
  }
  printk("\n");

  printk("Reader Pos:       ");
  for ( i = 0; i < mb->readOffset; i++) {
    printk(" ");
  }
  printk("R\n");

  printk("Writer Pos:       ");
  for ( i = 0; i < mb->writeOffset; i++) {
    printk(" ");
  }
  printk("W\n");


  // Done with information about the buffer
  up( &(mb->bufLock) );


  // Success!
  printk("#################################\n");
  return 0;

}


/*
  initMailbox: Initialize a given mailbox struct and all 
  parameters inside. 

  Parameters: struct mailbox * mb - mailbox struct to initialize
              int writeID - minor number of write end of mailbox
	      int readID  - minor number of read end of mailbox

  Returns: 0 on success; Errno on failure (cdev add fails), and we
  return the error code to pass back up to user
 */
static int initMailbox( struct mailbox * mb ,
			int writeID, 
			int readID ) {
  
  // Initialize some handy iterators and return values for later
  int err, i; 

  /* Mutex's that protect shared state */
  init_MUTEX( &mb->readLock  );                                 
  init_MUTEX( &mb->writeLock );
  init_MUTEX( &mb->bufLock   );
  init_MUTEX( &mb->blockedReader );
  init_MUTEX( &mb->blockedWriter );


  /* Information about blocked processes */
  mb->numWritersWaiting = 0;
  mb->numReadersWaiting = 0;
  mb->numWritersBlocked = 0;
  mb->numReadersBlocked = 0;

  /* Wait Queues that manipulate blocked processes waiting on some
     condition */
  init_waitqueue_head( &(mb->readQueue) );
  init_waitqueue_head( &(mb->writeQueue) );
  init_waitqueue_head( &(mb->blockedReaderQ) );
  init_waitqueue_head( &(mb->blockedWriterQ) );

  /* Offset Lengths */
  mb->readOffset = 0;
  mb->writeOffset = 0;
  
  /* Buffer data status */
  mb->numItems = 0;
  mb->numHoles = MYMAILBOXDEV_SIZE;

  /* Current Pid */
  mb->currRead = -1;
  mb->currWrite = -1; 

  /* Stored errno return values for prior failures */
  mb->errnoRead = 0;
  mb->errnoWrite = 0;

  /* Device minor numbers for read and write ends */
  mb->writeID = writeID;
  mb->readID = readID;

  // Initialize character device and struct on reader end
  cdev_init(&(mb->reader), &mbox_ops); 
  mb->reader.owner = THIS_MODULE;
  mb->reader.ops = &mbox_ops;

  err = cdev_add(&(mb->reader), MKDEV(MYMAILBOXDEV_MAJOR, readID), 1); 
  if(err) { 
    printk("ERROR: cdev_add failed\n"); 
    return err;
  }


  // Initialize character device and struct on writer end
  cdev_init(&(mb->writer), &mbox_ops); 
  mb->writer.owner = THIS_MODULE;
  mb->writer.ops = &mbox_ops;

  err = cdev_add(&(mb->writer), MKDEV(MYMAILBOXDEV_MAJOR, writeID), 1); 
  if(err) { 
    printk("ERROR: cdev_add failed\n"); 
    return err;
  }
  
  // Initialize the buffer to have '-', for easy printing and debugging
  for ( i = 0; i < MYMAILBOXDEV_SIZE; i ++ ){
    mb->buf[i] = '-';
  }

  // Initialization successful!
  return 0;

}

/*
  cleanMailbox: Clean up state associated with a mailbox, once our 
  module is being unloaded from the kernel.

  Parameters: struct mailbox * mb - mailbox to clean up, mainly by
  unregistering the character devices associated with the read and
  write end.

  Returns: 0
 */
static int cleanMailbox( struct mailbox * mb ) {

  // Unregister device driver
  cdev_del(&(mb->reader));
  cdev_del(&(mb->writer));

  return 0;

}

/*
  putChar: A helper function that safely inserts a single character
  into a mailbox buffer. If there is not enough space in the buffer,
  the caller blocks. If there are readers waiting on additional data,
  the caller wakes them up. Code largely taken from solution to
  Producer and Consumer problem using Binary semaphores only.

  Parameters: struct mailbox * mb - mailbox to add data to
              char c - character to add to buffer

  Returns: 0 on success; -EBUSY if there was an error acquiring a 
  needed mutex.

 */
static int putChar( struct mailbox * mb, char c ) {
  
  // Producer Code
  
  // Get our current task struct
  struct task_struct * ts;
  ts = current;

  // Reserve a space to put our character
  if ( down_interruptible( &(mb->blockedWriter) ) ) {
    return -EBUSY;
  }
  mb->numHoles --;
  if ( mb->numHoles < 0 ) {
    // Not enough space - buffer is full

    /* Block this process */
    ts->state = TASK_INTERRUPTIBLE;
    // Add ourselves to a waitqueue
    DECLARE_WAITQUEUE( wait_entry, ts );
    add_wait_queue_exclusive( &(mb->blockedWriterQ), &wait_entry );
    // Let the consumer know we're waiting
    mb->numWritersBlocked ++;

    up( &(mb->blockedWriter) );
    // Block
    schedule();
    
    // Return



    if ( down_interruptible( &(mb->blockedWriter) ) ) {
      return -EBUSY;
    }
    
    // Clean up after ourselves
    remove_wait_queue( &(mb->blockedWriterQ), &wait_entry );
    mb->numWritersBlocked --;
    
    if ( signal_pending( current ) ) {
      mb->numHoles ++;
    }

    up( &mb->blockedWriter );

    /* See if we have a pending signal */
    if ( signal_pending( current ) ) {
      return -EINTR;
    }


  }
  else {
    // We got a spot, and have reserved a space
    up( &mb->blockedWriter );
  }

  /* Once we get here we can put our character in the 
     buffer since there is space */
  
  // Lock state associated with shared buffer
  if ( down_interruptible( &(mb->bufLock) ) ) {
    return -EBUSY;
  }
  
  // Add our character to the buffer
  mb->buf[mb->writeOffset] = c;
  mb->writeOffset = (mb->writeOffset + 1) % MYMAILBOXDEV_SIZE;

  // Done updating state associated with buffer
  up( &mb->bufLock );

  // And, now we do an up to let the consumer know that 
  // we have put things in the buffer.

  // Lock shared state associated with blocked reader
  if ( down_interruptible( &(mb->blockedReader) ) ) {
    return -EBUSY;
  }
  // We've added something
  mb->numItems ++;
  if ( mb->numItems <= 0 ) {
    // Unblock a reader 
    wake_up( &(mb->blockedReaderQ) );
  }

  // Done with shared state associated with waiting reader
  up( &mb->blockedReader );
  
  // Success!
  return 0;

}

/*
  getChar: A helper function that safely reads a single character from
  a mailbox buffer. If there are not any characters in the buffer, the
  caller blocks. If there are writers waiting on additional space, the
  caller wakes them up. Code largely taken from solution to Producer
  and Consumer problem using Binary semaphores only.

  Parameters: struct mailbox * mb - mailbox to read data from
              char * c - character read from buffer

  Returns: 0 on success; -EBUSY if there was an error acquiring a 
  needed mutex.

 */
static int getChar( struct mailbox * mb, char * c ) {
  // Consumer Code

  // Get our current task struct
  struct task_struct * ts;
  ts = current;

  // Reserve an existing character in the buffer
  if ( down_interruptible( &(mb->blockedReader) ) ) {
    return -EBUSY;
  }
  mb->numItems --;
  if ( mb->numItems < 0 ) {
    // Not enough characters - buffer is empty

    /* Block this process */
    ts->state = TASK_INTERRUPTIBLE;
    DECLARE_WAITQUEUE( wait_entry, ts );
    // Add ourselves to a waitqueue
    add_wait_queue_exclusive( &(mb->blockedReaderQ), &wait_entry );
    // Let the producer know we're waiting
    mb->numReadersBlocked ++;

    up( &(mb->blockedReader) );
    // Block
    schedule();


    
    // Return
    if ( down_interruptible( &(mb->blockedReader) ) ) {
      return -EBUSY;
    }
    // Clean up after ourselves
    remove_wait_queue( &(mb->blockedReaderQ), &wait_entry );
    mb->numReadersBlocked --;
    
    /* See if we have a pending signal */
    if ( signal_pending( current ) ) {
      mb->numItems ++;
    }



    up( &mb->blockedReader );

    /* See if we have a pending signal */
    if ( signal_pending( current ) ) {
      return -EINTR;
    }

    

  }
  else {
    // We've reserved a character, and are good to go
    up( &mb->blockedReader );
  }

  // Once we get here we can take a character out of the 
  // buffer since there is a character in there that we've reserved
  if ( down_interruptible( &(mb->bufLock) ) ) {
    return -EBUSY;
  }
  
  // Read a character from the buffer, and update shared state
  *c = mb->buf[mb->readOffset];
  mb->readOffset = (mb->readOffset + 1) % MYMAILBOXDEV_SIZE;

  // Done with state associated with buffer
  up( &mb->bufLock );

  // And, now we do an up to let the producer know that 
  // we have taken things out of the buffer
  if ( down_interruptible( &(mb->blockedWriter) ) ) {
    return -EBUSY;
  }
  // There's new space!
  mb->numHoles ++;
  if ( mb->numHoles <= 0 ) {
    // Unblock a reader 
    wake_up( &(mb->blockedWriterQ) );
  }
  // Done with shared state associated with waiting writer
  up( &mb->blockedWriter );
  
  // Success
  return 0;


}


/*
 * File operations on mailbox devices (simplified due to top down design
 * and the helper functions above). 
 */


/*
  mychardev_read: Read a given number of characters from the mailbox,
  blocking as needed until enough characters have been read.

  Parameters: struct file * fp: File struct associated with open
                                file descriptor (in user space)
	      char __user * buff: Buffer to put read data into
	      size_t len: Number of characters to read from buffer
	      loff_t * offset: Unused; offsets maintained internally

  Returns: number of characters read, if num > 0. If none successfully,
           read, returns errno. If a prior call successfully read some 
	   elements and subsequently failed, will return the errno from
	   that call, without trying to do any reading. 

	   Possible Errorno Returns:
	   => EINVAL: Tried to read from write end of mailbox, or don't
	              have mailbox open to begin with
	   => EFAULT: Error accessing / copying to user space
	   =>  EBUSY: Error acquiring needed mutex
 */
ssize_t mychardev_read( struct file *fp, 
			char __user *buff, 
			size_t len,
			loff_t *offset)
{
  
  /* Variable declarations for later on. Keep gcc happy */
  struct task_struct * ts;          
  int i, ret, minorNum, mailboxNum; 
  char local[len]; // Local buffer for read in data
  char c;
  struct mailbox * mb; // Current mailbox

  // Get our current mailbox. The mailbox minor device num
  // is stored in the private data field of the fp struct.
  
  minorNum = *(int*)(fp->private_data);
  mailboxNum = minorNum / 2 ;
  mb = &mailboxes[ mailboxNum ];
  
  /* Check if we have a pending errno to return */
  if ( mb->errnoRead ) {
    ret = mb->errnoRead;
    mb->errnoRead = 0;
    return -ret;
  }

  // Check if the mailbox is valid to read from
  if ( ! ( minorNum % 2) ) {
    // Trying to read from a write end
    return -EINVAL;
  }

  // Check valid pointer in user space
  if ( ! access_ok( VERIFY_WRITE, buff, sizeof( char ) * len ) ) {
    return -EFAULT;
  }

  // Check that the buffer is valid for writing before 
  // removing anything from the mailbox.
  if ( copy_from_user( local, buff, sizeof(char)*len ) ) {
    return -EFAULT;
  }


  printk("Past access ok!\n");

  // Get our current task struct
  ts = current;

  /* Check that we are the current reader (by comparing current
     pid to stored reader pid */
  if ( down_interruptible( &(mb->readLock) ) ) {
    return -EBUSY;
  }
  if (ts->pid != mb->currRead) {
    up( &mb->readLock );
    return -EINVAL; // We're not the right PID
  }
  up( &mb->readLock );
  
  /* Finally, we can start reading some data from the buffer */
  for ( i = 0; i < len; i ++ ) {
    // Get as many characters as we need
    if ( (ret = getChar( mb, &c )) ) {
      // Something went wrong getting a character
      if ( i ) {
	// We've read some things successfully though, so we need
	// to store errno for next call and return number of chars
	// read.
	mb->errnoRead = -ret;
	return i;
      }
      // Nothing read successfully - just return errno
      return ret;
    }
    // Character was gotten successfully; update local buffer
    local[i] = c;
  }
  
  // Copy the results back to the user
  if ( copy_to_user( buff, local, sizeof(char)*len ) ) {
    return -EFAULT;
  }

  // Return number of characters successfully read
  return len;
}


/*
  mychardev_write: Write a given number of characters to the mailbox,
  blocking as needed until characters have been written.

  Parameters: struct file * fp: File struct associated with open
                                file descriptor (in user space)
	      char __user * buff: Buffer to copy data from
	      size_t len: Number of characters to put in buffer
	      loff_t * offset: Unused; offsets maintained internally

  Returns: number of characters written, if num > 0. If none successfully,
           written, returns errno. If a prior call successfully wrote some 
	   elements and subsequently failed, will return the errno from
	   that call, without trying to do any writing. 

	   Possible Errorno Returns:
	   => EINVAL: Tried to write to read end of mailbox, or don't
	              have mailbox open to begin with
	   => EFAULT: Error accessing / copying from user space
	   =>  EBUSY: Error acquiring needed mutex
 */
ssize_t  mychardev_write(struct file *fp, 
			 const char __user *buff,
			 size_t len, 
			 loff_t *offset)
{
  /* Keep gcc happy by declaring things at top of functions */
  struct task_struct * ts;
  int i, ret, minorNum, mailboxNum;
  char local[len]; // Local buffer of data to write
  struct mailbox * mb; // Current mailbox to write to
  
  // Get our current task struct
  ts = current;
  
  
  // Get mailbox minor number, which is stored in the private_data
  // field of the fp struct. Use this to get the mailbox as well.
  minorNum = *(int*)(fp->private_data);
  mailboxNum = minorNum / 2 ;
  mb = &mailboxes[ mailboxNum ];

  /* Check if we have a pending errno to return */
  if ( mb->errnoWrite ) {
    ret = mb->errnoWrite;
    mb->errnoWrite = 0;
    return -ret;
  }

  /* Check that we're not trying to write to a read end */
  if ( minorNum % 2 ) {
    return -EINVAL;
  }
  
  // Check valid pointer in user space
  if ( ! access_ok( VERIFY_READ, buff, sizeof( char ) * len ) ) {
    return -EFAULT;
  }
  // Copy over their data into kernel space
  if ( copy_from_user( local, buff, sizeof(char) * len ) ) {
    return -EFAULT;
  }

  /* Check that we have this mailbox open to begin with */
  if ( down_interruptible( &(mb->writeLock) ) ) {
    return -EBUSY;
  }
  if (ts->pid != mb->currWrite) {
    up( &mb->writeLock );
    return -EINVAL;
  }
  up( &mb->writeLock );
  

  // Finally, write the data to the buffer, one character at
  // a time
  for ( i = 0; i < len; i ++ ) {
    if ( (ret = putChar( mb, local[i] )) ) {
      // Something went wrong writing character to buffer
      if ( i ) {
	// We've written some things successfully though, so we need
        // to store errno for next call and return number of chars
        // written.
	mb->errnoWrite = -ret;
	printk("Something went wrong writing. Returining after %d bytes\n",
	       i);
	return i;
      }
      // Nothing written successfully - just return errno
      return ret;
    }
  }
  
  // Return number of characters written successfully
  return len;
}


/*
  mychrdev_open: Initialize a character device for subsequent reading
  / writing from a given process.

  Parameters: struct inode * in: Inode for the device that we're
                                 opening for the user
	      struct file * fp: Process specific file struct 
	                        that we're opening for user

  Returns 0 upon success, or sets errno if failure.
  => ENOMEM: Not enough memory to allocate needed data fields
  => EBUSY : Error acquiring needed mutex
  => EDEADLOCK : Trying to open a mailbox we already own and will deadlock
 */
int mychrdev_open(struct inode *in, struct file *fp) { 
  
  /* Keep gcc happy by declaring most variables at the top of functions */
  struct mailbox * mb;
  int reading;
  int mailboxNum;
  struct task_struct * ts;
  
  // Get our current task struct
  ts = get_current() ;
  
  // Find the appropriate mailbox in mailboxes array, and determine
  // if we're opening a read end or write end
  mailboxNum = iminor( in ) / 2 ;
  reading = (iminor( in )) % 2; // Even numbers are write ends;
  
  mb = &mailboxes [ mailboxNum ];


  /* Use the private_data field to store the inode minor
     number. */
  int * minorPtr = kmalloc( sizeof(int), GFP_KERNEL );
  if ( ! minorPtr ) {
    return -ENOMEM;
  }
  *minorPtr = iminor( in );
  fp->private_data = minorPtr;

  /* Do the appropriate initialization for readers or writers */

  if ( reading ) {
    // Opening read end
    
    // Lock the reader lock
    if ( down_interruptible( &(mb->readLock) ) ) {
      return -EBUSY;
    }
    if ( mb-> currRead == -1 ) {
      // We're the first ones! The read end is ours to command!
      mb->currRead = ts->pid;
      up( &(mb->readLock));
    }
    else if ( mb->currRead == ts->pid ) {
      // Don't deadlock waiting for the mailbox if we already
      // own it.
      up( &(mb->readLock));
      return -EDEADLOCK; 
    }
    else {
      // Somebody else is reading Block until they're finished
      ts->state = TASK_INTERRUPTIBLE;
      DECLARE_WAITQUEUE( wait_entry, ts );
      add_wait_queue_exclusive( &(mb->readQueue), &wait_entry );
      mb->numReadersWaiting ++; // Let them know we're waiting
      up( &(mb->readLock) );
      // Block
      schedule();
      // Return
      if ( down_interruptible( &(mb->readLock) ) ) {
	return -EBUSY;
      }
      // Clean up after ourselves
      remove_wait_queue( &(mb->readQueue), &wait_entry );
      mb->numReadersWaiting --; 

      // Claim the read end as our own
      mb->currRead = ts->pid;

      // Done with shared state for reader of mailbox
      up( &(mb->readLock) );
    }
  }
  else {
    // Opening write end

    // Lock the writer lock
    if ( down_interruptible( &(mb->writeLock) ) ) {
      return -EBUSY;
    }
    if ( mb-> currWrite == -1 ) {
      // We're the first ones! The write end is ours to command!
      mb->currWrite = ts->pid;
      up( &(mb->writeLock));
    }
    else if ( mb->currWrite == ts->pid ) {
      // Don't deadlock waiting for the mailbox if we already
      // own it.
      up( &(mb->writeLock));
      return -EDEADLOCK; 
    }
    else {
      // Somebody else is writing. Block until they're finished
      DECLARE_WAITQUEUE( wait_entry, ts );

      ts->state = TASK_INTERRUPTIBLE;
      add_wait_queue_exclusive( &(mb->writeQueue), &wait_entry );
      mb->numWritersWaiting ++; // Let them know we want to write too.
      up( &(mb->writeLock) );
      // Block
      schedule();
      // Return
      if ( down_interruptible( &(mb->writeLock) ) ) {
	return -EBUSY;
      }
      // Clean up after ourselves
      remove_wait_queue( &(mb->writeQueue), &wait_entry );
      mb->numWritersWaiting --;

      // Claim the write end of the mailbox
      mb->currWrite = ts->pid;
      up( &(mb->writeLock) );
    }
  }

  /* When we get here, we're the only person writing or reading.
     We have the mailbox (end) all to ourselves. :) */
  printk("Opening device maj %u  minor %u\n", imajor( in ), iminor( in ) );
  
  return 0;
}


/*
  mychardev_release: Clean up state associated with a open device
  when a process is done using it.

  Parameters: struct inode * in: Inode for the device that we're
                                 closing for the user
	      struct file * fp: Process specific file struct 
	                        that we're closing for user
  Returns 0 upon success, or sets errno if failure.
  => EBUSY : Error acquiring needed mutex
 */
int mychardev_release(struct inode *in, struct file *fp){
  
  /* Keep gcc happy by declaring things at the top of functions */
  struct mailbox * mb;
  int mailboxNum;
  int reading;
  
  // Get the mailbox minor number, determine if closing a read or
  // write end, and get a pointer to our mailbox
  mailboxNum = iminor( in ) / 2 ;
  reading = (iminor( in )) % 2; // Even numbers are write ends;
  mb = &mailboxes [ mailboxNum ];

  // Let the implementers know what's happening down here in the
  // kernel
  printk("Closing %s end of mailbox %d\n", 
	 (reading ? "read" : "write"), mailboxNum);
  
  // Free the stored inode minor number stored in fp's private_data
  // field
  kfree( fp->private_data );

  // Reset the necessary state variables, and wake up a process
  // if it's waiting. 
  if ( reading ) {

    // Lock shared reading state variables
    if ( down_interruptible( &(mb->readLock) ) ) {
      return -EBUSY;
    }

    // Reset the current reader pid
    mb->currRead = -1;
    
    // Reset any pending errnos
    mb->errnoRead = 0;

    // If somebody's waiting, wake them up
    if ( mb-> numReadersWaiting ) {
      wake_up( &(mb->readQueue) ); // This wakes up a single process
                                   // Since we set EXCLUSIVE flag when
                                   // adding. 
    }
    // Done with shared reader state
    up( &(mb->readLock) );

  }
  else {
    // Closing down the write end

    // Lock shared writing state variables
    if ( down_interruptible( &(mb->writeLock) ) ) {
      return -EBUSY;
    }
    
    // Reset current writer PID
    mb->currWrite = -1;

    // Reset any pending errnos
    mb->errnoWrite = 0;
    
    // If there are others waiting, wake one up
    if ( mb-> numWritersWaiting ) {
      wake_up( &(mb->writeQueue)); // This wakes up a single process
                                   // Since we set EXCLUSIVE flag before
                                   // adding. 
    }
    // Done with shared writer state
    up( &(mb->writeLock) );
  }
  
  // Success!
  return 0;
}


/*
  mychardev_ioctl: Print out information about all mailboxes

  Parameters: struct inode * in, struct file * fp, and two unused
  parameters, which are unused in our implementation but provided by
  the OS if we wanted to use them.

  Returns: 0 upon success; -EBUSY if error acquiring mutex for 
  shared state.
 */
int mychardev_ioctl(struct inode *in, struct file *fp,
    unsigned int unused1, unsigned long unused2) {

  // Keep gcc happy by initailizing variables at top
  // of functions
  int i, ret;
  ret = 0;

  // Print each mailbox
  printk("==================================\n");

  for ( i = 0; i < MYMAILBOXDEV_NUM / 2; i ++ ) {
    if ( printMailbox( &mailboxes[i] ) ) {
      printk("Error Printing Mailbox %d!!\n", i);
      ret = -EBUSY; // Error is with locking required mutex
    }
  }
  
  printk("==================================\n");

  // Return status indication
  return ret;

}


/***********************************************************/
/*
 * Routines called when module is loaded/unloaded
 */
/***********************************************************/
/*
  init_mailbox: Load a mailbox driver module, register
  character devices, and initialize our mailboxes.

  Parameters: None.

  Returns: 0 on success; on failure due to cdev_add failing,
  returns the error value set by cdev_add.
 */
static __init int init_mailbox(void) {

  int i, ret;

  printk(KERN_INFO "loading mailbox device driver module\n"); 

  // Allocate device numbers associated with our device
  if( (ret = register_chrdev_region(MKDEV(MYMAILBOXDEV_MAJOR,0), 
				    8, MYMAILBOXDEV_NAME)))  {
    printk("ERROR: register_chardev_region failed\n");
    return ret; // Pass up register_chrdev_region error code
  }
  
  
  // Register and initialize our character devices
  for ( i = 0; i < MYMAILBOXDEV_NUM / 2; i ++ ) {
    if ( ( ret = initMailbox( & (mailboxes[i]), 2*i, 2*i+1 ) ) ) {
      printk("Error initializing mailbox %d\n", i);
      return ret; // Errno passed up from cdev_add failure
    }
    else {
      printk("Initialized mailbox %d\n", i);
    }
  }
  
  // Success!
  return 0;
}

/*
  cleanup_mailbox: Removes state associated with a mailbox that is
  being closed upon lkm being removed from the system.

  Parameters: None.
  
  Returns: None.
 */
static void __exit cleanup_mailbox(void) {
  
  // Keep gcc happy by declaring things at the beginning
  int i;
  
  printk(KERN_INFO "removing mailbox device driver module\n"); 
  
  // Clean up our mailboxes
  for ( i = 0 ; i < MYMAILBOXDEV_NUM / 2; i ++ ) {
    cleanMailbox( &(mailboxes[i]) );
  }

  // Free the allocated device numbers associated with our device
  unregister_chrdev_region(MKDEV(MYMAILBOXDEV_MAJOR, 0), 8);
}
/***********************************************************/

// Let Linux know how to initialize and close this module
module_init(init_mailbox);
module_exit(cleanup_mailbox);
MODULE_LICENSE("GPL"); // Yay open source!
